#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
 

示例 1:



输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。


来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
TODO 分多钟情况

 * */

//返回删除后的头节点
TreeNode* deleteNode(TreeNode*& root, int key) {

    if (root== nullptr)
        return root;

    //
    if (root->val==key)
    {
        //如果右边不空左边空
        if (root->right&& !root->left)
        {

            root->val=root->right->val;
            root->right= root->right->right;

            //如果 左边不空右边空
        } else if (!root->right&& root->left)
        {
            root->val=root->left->val;
            root->left= root->left->left;

            //要删除的左右子树都存在 则寻找柚子树 最左节点
        } else if (root->right&& root->left){

            TreeNode* tem=root->right;
            TreeNode* pre=root->left;
            while (tem->left)
            {
                pre=tem->left;
                tem=tem->left;
            }

            root->val= pre->val;

            *(TreeNode**)pre= nullptr;






           // root->val=root->right->val;
           // root->right=root->right->right;

        } else {
            root= nullptr;
        }

    }

    if (root&&root->val>key)
    {
        deleteNode(root->left,  key);
    }
    if (root&&root->val<key)
    {
        deleteNode(root->right,  key);
    }

    return root;
}

//返回删除后的 新的root
//todo 我擦我写的不对。。。。
//TreeNode* deleteNode(TreeNode* root, int key)
//{
//
//    if (root== nullptr)
//        return root;
//
//    if (root->val==key)
//    {
//        //第一种 必须这样写 要不少了一个 左右都为null的情况 这种就是都包含了 左边右边都是空了
//        if (root->left== nullptr)
//            return root->right;
//        else if (root->right== nullptr)
//            return root->left;
//        else
//        {
//            //如果左边右边都不为null 取右子树的最左边
//
//            TreeNode* cur = root->right; // 找右⼦树最左⾯的节点
//            while(cur->left != nullptr) {
//                cur = cur->left;
//            }
//            cur->left = root->left; // 把要删除的节点（root）左⼦树放在cur的左孩⼦的位置
//
//            //不要 cur->right=root->left 右边挂着东西呢
//            TreeNode* tmp = root; // 把root节点保存⼀下，下⾯来删除
//            root = root->right; // 返回旧root的右孩⼦作为新root
//            delete tmp;
//
//            return root;
//
//        }
//
//
//
//
//    }
//
//
//
//
//
//    root->left = deleteNode(root->left, key);
//     root->right = deleteNode(root->right, key);
//    return root;
//
//}
//这个思路就是把 他妈的有问题的节点去除了
//同样返回修剪后的树的头结点
//TODO 我草我真的是想不起来 真的傻逼了这个题
// 有点不太明白修建二叉树和这个去呗
TreeNode* trimBST(TreeNode* root, int low, int high)
{
    if (!root)
        return root;


    if (root->val<low){

        return trimBST(root->right,  low,  high);
    }

    if (root->val > high) {

        return trimBST(root->left, low, high);
    }

    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);

    return root;

}

//
TreeNode *deleteNode(TreeNode *root, int key) {

    if (root == nullptr)
        return root;

    //其实他这个删除跟书上学的有差距 这个删除的思路比较简单

    if (root->val == key) {
        //如果要删除的节点左边节点为null
        if (!root->left) {
            //这边你就想象两个节点 如果你把跟删除了 左边为null
            //只能把右边当成根节点了
            return root->right;
        }
        if (!root->right) {
            //同理
            return root->left;
        }

        if (root->left && root->right) {
            //如果都不null 寻找右边端点的最左边的孩子
            //然后把要删除的节点的左边都挂到 这个节点上
            //然后把root=root.right 就行
            //所以跟咱们学的不太一样咱们学的得保存前置指针
            auto right = root->right;

            while (right->left) {
                right = right->left;
            }
            //获得了最左边节点 保存到right

            right->left = root->left;

            root = root->right;

            return root;//删除完毕返回跟这个想法类似上面那个

        }

    } else if (key < root->val)
        root->left = deleteNode(root->left, key);
    else {
        root->right = deleteNode(root->right, key);
    }

    return root;
}













